import functools


# 记忆化搜索带剪枝
# class Solution(object):
#     def stoneGameV(self, stoneValue):
#         n = len(stoneValue)
#         prefix = stoneValue.copy()
#         for i in range(1, n):
#             prefix[i] += prefix[i - 1]
#         @functools.cache
#         def dfs(i, j):
#             if i == j:
#                 return 0
#             else:
#                 if i == 0:
#                     total = prefix[j]
#                 else:
#                     total = prefix[j] - prefix[i - 1]
#                 pre = 0
#                 max_val = 0
#                 for k in range(i, j):
#                     pre += stoneValue[k]
#                     if 2 * pre < total:
#                         max_val = max(max_val, pre + dfs(i, k))
#                     else:
#                         if 2 * pre == total:
#                             max_val = max(max_val, pre + max(dfs(i, k), dfs(k + 1, j)))
#                         else:
#                             if max_val >= 2 * (total - pre):
#                                 break
#                             max_val = max(max_val, total - pre + dfs(k + 1, j))
#                 return max_val
#         return dfs(0, n - 1)

# O(n^2)
class Solution(object):
    def stoneGameV(self, stoneValue):
        n = len(stoneValue)
        f = [[0] * n for _ in range(n)]
        maxl = [[0] * n for _ in range(n)]
        maxr = [[0] * n for _ in range(n)]
        for left in range(n - 1, -1, -1):
            t_sum = stoneValue[left]
            left_sum = stoneValue[left]
            i0 = left
            maxl[left][left] = stoneValue[left]
            maxr[left][left] = stoneValue[left]
            for right in range(left + 1, n):
                t_sum += stoneValue[right]
                while 2 * left_sum < t_sum:
                    i0 += 1
                    left_sum += stoneValue[i0]
                if 2 * left_sum == t_sum:
                    f[left][right] = max(maxl[left][i0], maxr[i0 + 1][right])
                else:
                    if i0 > left:
                        f[left][right] = maxl[left][i0 - 1]
                    if i0 + 1 <= right:
                        f[left][right] = max(f[left][right], maxr[i0 + 1][right])
                maxl[left][right] = max(maxl[left][right - 1], f[left][right] + t_sum)
                maxr[left][right] = max(maxr[left + 1][right], f[left][right] + t_sum)
        return f[0][n - 1]

data = Solution()
stoneValue = [6, 2, 3, 4, 5, 5]
print(data.stoneGameV(stoneValue))
